package leetcode_day._2021._202106._1120;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/19 23:12
 * 串联字符串的最大长度
 * 算法：位运算  回溯
 * 1、把字符串转化成二进制位数
 * 2、在转化的过程中去除掉自身字符重复的字符串
 * 3、使用回溯，列出每一种可能
 */
public class _19_1239 {
    public static void main(String[] args) {
        System.out.println(new _19_1239().maxLength(new ArrayList<>(Arrays.asList("cha","r","act","ers"))));
    }

    int ans = 0;
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        for (String s : arr) {
            int mask = 0;
            for (char c : s.toCharArray()) {
                int x = c - 'a';
                if ((mask >> x & 1) == 1) {
                    mask = 0;
                    break;
                }
                mask |= 1 << x;
            }
            if (mask > 0) masks.add(mask);
        }
        dfs(masks, 0, 0);
        return ans;
    }
    void dfs(List<Integer> masks, int start, int res) {
        if (start == masks.size()) {
            ans = Math.max(ans, Integer.bitCount(res));
            return;
        }
        for (int i = start; i < masks.size(); i++) {
            if ((res & masks.get(i)) == 0) dfs(masks, i + 1, res | masks.get(i));
            dfs(masks, i + 1, res);
        }
    }

}
